#include<iostream>
#include "List.h"
using namespace std;

//带头结点单链表的初始化
bool Init_HeadLNode(LinkList &L)
{
	//首先创建头结点
	L = new LNode;
	L->next = NULL;

	if (L == NULL)
	{
		cout << "分配失败" << endl;
		return false;
	}
	return true;
}

//使用头插法创建一个单链表
bool Create_front_LNode(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;

	while (n != 0)
	{
		LNode* s = new LNode;
		cin >> s->data;
		s->next = L->next;
		L->next = s;
		n--;
	}

	return true;
}

//使用尾插法创建一个单链表
bool Create_behind_LNode(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	LNode* r = L;
	int i;
	for (i = 0; i < n; i++)
	{
		LNode* s = new LNode;
		cin >> s->data;
		s->next = NULL;
		r->next = s;
		r = s;
	}
	return true;
}
//-----------插入删除有问题-----------------
//带头节点单链表的插入元素  --时间复杂度为--
int Insert_HeadLNode(LinkList &L, int i, int e)
{
	LNode* p = L;
	int j = 0;

	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		cout << "i值错误" << endl;
		return false;
	}
	//此时p已经指向了第i-1个节点
	LNode* s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 0;
}

//带头结点单链表删除元素  --时间复杂度为--
int Delete_HeadLNode(LinkList &L, int i)
{
	//在单链表中要想对第i个节点进行操作的话，必须先找到第i-1个节点
	LNode* p = L;
	int j = 0;

	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		cout << "i值错误" << endl;
		return false;
	}
	//此时p已经指向了第i-1个节点,新建一个节点指向第i个节点，用来释放该节点内存
	LNode* q = p->next;
	p->next = q->next;

	delete q;
	return 0;
}


//带头结点单链表的查找（使用值来查找元素位置）返回元素值位置 --时间复杂度--
LNode* Search_HeadLNode(LinkList& L, int e)
{
	LNode* p = L->next;

	while (p && p->data != e)
		p = p->next;

	return p;
}

//带头结点单链表的取值（使用位置来取得相应元素的值）返回值  --时间复杂度--
int Get_HeadLNode(LinkList& L, int i)
{
	int j = 0;
	LNode* p = L -> next;

	while (j < i - 1 && p)
	{
		p = p->next;
		j++;
	}
	if (!p)
	{
		cout << "i值超出范围" << endl;
		return false;
	}
	return p->data;
}

//销毁单链表
bool Destory_HeadLNode(LinkList& L)
{
	LNode* p = L;
	while (p)
	{
		LNode* tmp = p->next;
		delete p;
		p = tmp;
	}
	L = nullptr;
	if (!p && !L)
		cout << "销毁完成" << endl;

	return true;
}